//给你二叉树的根结点 root ，请你将它展开为一个单链表： 
//
// 
// 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。 
// 展开后的单链表应该与二叉树 先序遍历 顺序相同。 
// 
//
// 
//
// 示例 1： 
// 
// 
//输入：root = [1,2,5,3,4,null,6]
//输出：[1,null,2,null,3,null,4,null,5,null,6]
// 
//
// 示例 2： 
//
// 
//输入：root = []
//输出：[]
// 
//
// 示例 3： 
//
// 
//输入：root = [0]
//输出：[0]
// 
//
// 
//
// 提示： 
//
// 
// 树中结点数在范围 [0, 2000] 内 
// -100 <= Node.val <= 100 
// 
//
// 
//
// 进阶：你可以使用原地算法（O(1) 额外空间）展开这棵树吗？ 
//
// Related Topics 栈 树 深度优先搜索 链表 二叉树 👍 1526 👎 0


package LeetCode.editor.cn;

import java.util.Stack;

/**
 * @author ldltd
 * @date 2023-08-19 03:27:47
 * @description 114.二叉树展开为链表
 */
public class FlattenBinaryTreeToLinkedList{
	 public static void main(String[] args) {
	 	 //测试代码

         TreeNode tree1 = new TreeNode(1);
         tree1.left = new TreeNode(2);
         tree1.right = new TreeNode(5);
         tree1.left.left = new TreeNode(3);
         tree1.left.right = new TreeNode(4);
         tree1.right.right = new TreeNode(6);
         Solution solution = new FlattenBinaryTreeToLinkedList().new Solution();
         solution.printTree(tree1);
         solution.flatten(tree1);
         solution.printTree(tree1);
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)

 // Definition for a binary tree node.
  public static class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }

class Solution {
    public void flatten(TreeNode root) {
        //辅助节点
        TreeNode p=null;
        //保存头结点
        TreeNode t=root;
        while (t!=null){
            if(t.left!=null){
                p=t.left;
                //找到左子树的最右节点
                while (p.right!=null&&p.right!=t){
                    p=p.right;
                }
                // 如果 p 的右指针为空，将其指向 root，继续遍历左子树
                if(p.right==null){
                    TreeNode rightSubtree = t.right; // 保存右子树的引用
                    p.right = rightSubtree; // 将右子树连接到左子树的最右节点
                    t.right = t.left; // 将左子树移动到右子树位置
                    t.left = null; // 清空左子树
                    t = rightSubtree; // 移动到下一个节点
                }
                // 如果 p 的右指针不为空，说明已经访问过左子树
                else {
                    p.right=t.right;
                    t.right=null;
                    t=p.right;
                }
            }
            // 如果没有左子树，直接移动到右子树
            else{
                t=t.right;
            }
        }
        // 重置为原始根节点
        p=root;
        t=root;
        //然后整理
        while (p != null) {
            if (p.left != null) {
                TreeNode rightMost = p.left;
                while (rightMost.right != null) {
                    rightMost = rightMost.right;
                }
                rightMost.right = p.right;
                p.right = p.left;
                p.left = null;
            }
            p = p.right;
        }
    }

    public void printTree(TreeNode root) {
        printTree(root, 0);
    }

    private void printTree(TreeNode node, int depth) {
        if (node == null) {
            return;
        }

        printTree(node.right, depth + 1);

        for (int i = 0; i < depth; i++) {
            System.out.print("   "); // 控制节点之间的间距
        }
        System.out.println(node.val);

        printTree(node.left, depth + 1);
    }
    /*gpt解法  莫里斯
    * 把左子树的最右节点连接到根的右节点，
    * 再把根的右子树连接改成左子树，
    * 根移动到右节点，依次循环到null也就是右子树的底部
    * 将左子树插入到右子树的地方
    * 将原来的右子树接到左子树的最右边节点
    * 考虑新的右子树的根节点，一直重复上边的过程，
    * 直到新的右子树为 null*/
    public void flatten1(TreeNode root) {
        TreeNode current = root;

        while (current != null) {
            if (current.left != null) {
                TreeNode rightmost = current.left;
                //找到左子树最右节点
                while (rightmost.right != null) {
                    rightmost = rightmost.right;
                }
                //他的右子树指向当前节点的右子树
                rightmost.right = current.right;
                //将左子树清空
                current.right = current.left;
                current.left = null;
            }
            current = current.right;
        }
    }

    /*递归
    * 后续遍历，右左根，然后返回就是根左右的顺序，将上一个节点保存，然后赋值*/
    private TreeNode pre = null;

    public void flatten2(TreeNode root) {
        if (root == null)
            return;
        flatten2(root.right);
        flatten2(root.left);
        root.right = pre;
        root.left = null;
        pre = root;
    }
    /*同理迭代右左根*/
    public void flatten3(TreeNode root) {
        Stack<TreeNode> toVisit = new Stack<>();
        TreeNode cur = root;
        TreeNode pre = null;

        while (cur != null || !toVisit.isEmpty()) {
            while (cur != null) {
                toVisit.push(cur); // 添加根节点
                cur = cur.right; // 递归添加右节点
            }
            cur = toVisit.peek(); // 已经访问到最右的节点了
            // 在不存在左节点或者右节点已经访问过的情况下，访问根节点
            if (cur.left == null || cur.left == pre) {
                toVisit.pop();
                /**************修改的地方***************/
                cur.right = pre;
                cur.left = null;
                /*************************************/
                pre = cur;
                cur = null;
            } else {
                cur = cur.left; // 左节点还没有访问过就先访问左节点
            }
        }
    }

    /*先序遍历会丢失右孩子，除了递归或用栈用后序遍历
    * 还可以用其他方法，提前把右孩子入栈
    * 先将右节点入栈
    * 利用先序遍历的代码，每遍历一个节点，
    * 就将上一个节点的右指针更新为当前节点。*/
    public void flatten4(TreeNode root) {
        if (root == null){
            return;
        }
        Stack<TreeNode> s = new Stack<TreeNode>();
        s.push(root);
        TreeNode pre = null;
        while (!s.isEmpty()) {
            //当前节点
            TreeNode temp = s.pop();
            //更新上一节点
            if(pre!=null){
                pre.right = temp;
                pre.left = null;
            }
            //右左的顺序入栈
            if (temp.right != null){
                s.push(temp.right);
            }
            if (temp.left != null){
                s.push(temp.left);
            }
            //更新pre
            pre = temp;

        }
    }

}
//leetcode submit region end(Prohibit modification and deletion)

}
